Buffers are temporary storage areas, usually in random access memory (RAM). Typically, buffers operate as a holding area, enabling a central processing unit (CPU) to manipulate data before transferring the data held in the buffer to a device. A particular type of buffer is a first in, first out (FIFO) queue. A FIFO queue is a buffer in which the first entry written to the buffer is the first entry read from the buffer. The entry which has been in the FIFO queue for the longest period of time is the first entry read from the queue.
When multiple entry types are stored in a FIFO queue in RAM, a separate buffer is required for each entry type stored in order to maintain FIFO ordering within the multiple entry types. Entries can have differing priorities depending on the entry type.
One prior solution for handling multiple entry types is to use one standard FIFO queue for each entry type. For example, assume that there are two different entry types, type A and type B. The prior solution required one FIFO queue for type A and another FIFO queue for type B.
Although strict FIFO rules are followed within any one entry type, frequently multiple entry types follow different ordering rules between them. For example, ordering rules for the two example entry types A and B are as follows:                1) Within each entry type, all entries must be read from the queue in the order in which they are written to the queue;        2) One or more type A entries may be read from the queue ahead of type B entries which were written to the queue ahead of the type A entries, but type B entries may not be read from the queue ahead of type A entries which were written to the queue ahead of the type B entries.        
To handle such ordering rules in addition to storing the type B entries, FIFO queue B also stores an extra “index” field with each entry corresponding to the write index, e.g. a pointer, to FIFO queue A at the time that the entry was placed in FIFO queue B. Then, in the prior solution, when attempting to remove an entry from FIFO queue B, i.e. the first entry (also referred to as the head entry) of the queue, the index field of the FIFO B entry is compared with the index field of the head entry of FIFO A. The FIFO B entry is not removed from the queue unless the index field of the head FIFO B entry is older than the index field of the head FIFO A entry.
According to the prior art, if the FIFO queue was implemented using a single unordered buffer, then (1) a read pointer pointing to the memory location, i.e. memory address, of the oldest entry in the queue and (2) a write pointer pointing to one entry behind the youngest entry in the queue must be maintained. In this case, the head and the tail of the queue (the oldest and youngest entries, respectively) can be anywhere in memory. Typically, the buffer will be considered empty when the read and write pointers point to the same address, and will be considered full when the write pointer points to one address in memory before the address pointed to by the read pointer. A “roll-over” case occurs when entries are continuously placed in the queue until the write pointer is advanced to the end of the buffer and an attempt is made to place further entries in the queue. If the read pointer is at the very start of the buffer, the buffer will be considered full, and the further entries are not placed in the queue. However, if the read pointer is not at the start of the buffer, the write pointer will “roll-over” the end of the buffer and return to the beginning. This arrangement is very complex and introduces a high potential for error.
The primary disadvantage of the prior art solution is that multiple FIFO buffer structures (such as a register array, RAM, etc.) of the same depth are required, because an entry stream could consist entirely of one entry type, or a mixture of entry types. This results in only a fraction of the storage space being used at any time while requiring the maximum allocation of memory space for each entry type. Another disadvantage is that the logic for handling the address roll-over case is complex and therefore increases the chance of errors.